# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/8/4
# @File : 完全背包问题.py
# 每个商品可以选无限次！

def dp_WQBeibao(char,n,v):
    dp = [[0]*(v+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,v+1):
            if(j < char[i][0]):
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-char[i][0]]+char[i][1])#这一步隐含着很深的推导，为什么少了一个循环，是要有数学公示的推导的。推导看题解视频
    return dp[-1][-1]
if __name__ == "__main__":
    n,v = map(int ,input().split())
    char = [[0,0]]
    for _ in range(n):
        rate = [int(i) for i in input().split()]
        char.append(rate)
    print(dp_WQBeibao(char,n,v))

#
# def dp_WQBeibao(char,n,v):
#     dp = [[0]*(v+1) for _ in range(n+1)]
#     for i in range(1,n+1):
#         for j in range(1,v+1):
#             if(j < char[i][0]):
#                 dp[i][j]=dp[i-1][j]
#             else:
#                 a = 0
#                 for k in range(1,j//char[i][0]+1):
#                     a = max(a,dp[i-1][j-k*char[i][0]]+k*char[i][1])
#                 dp[i][j]=max(dp[i-1][j],a)
#     return dp[-1][-1]
# if __name__ == "__main__":
#     n,v = map(int ,input().split())
#     char = [[0,0]]
#     for _ in range(n):
#         rate = [int(i) for i in input().split()]
#         char.append(rate)
#     print(dp_WQBeibao(char,n,v))

"""
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j]=max(f[i,j-v]+w , f[i-1][j]) 
"""